home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / SCIENCE / NTUMIN10.ZIP / LOGMIN_B.C < prev    next >
C/C++ Source or Header  |  1992-03-12  |  19KB  |  559 lines
  1. /****************************************************************************
  2.  *
  3.  *      Program name : LOGMIN_B.C
  4.  *
  5.  *    Written By : Eng-Huat Ong and Kian-Mong Low.
  6.  *
  7.  *      This is the actual minimization algorithm with slight modification
  8.  *    from the original LOGMIN algorithm. In phase II, in selecting the
  9.  *    adjacent, mi to shrink off, the 1st one with largest wi and is
  10.  *    already covered is chosen.
  11.  *
  12.  * --------------------------------------------------------------------------
  13.  *    Copyright (c) 1992. All Rights Reserved. Nanyang Technological
  14.  *    University.
  15.  *
  16.  *    You are free to use, copy and distribute this software and its
  17.  *    documentation providing that:
  18.  *
  19.  *        NO FEE IS CHARGED FOR USE, COPYING OR DISTRIBUTION.
  20.  *
  21.  *        IT IS NOT MODIFIED IN ANY WAY.
  22.  *
  23.  *        THE COPYRIGHT NOTICE APPEAR IN ALL COPIES.
  24.  *
  25.  *    This program is provided "AS IS" without any warranty, expressed or
  26.  *    implied, including but not limited to fitness for any particular
  27.  *    purpose.
  28.  *
  29.  *    If you find NTUMIN fast, easy, and useful, a note or comment would be
  30.  *    appreciated. Please send to:
  31.  *
  32.  *        Boon-Tiong Tan or Othman Bin Ahmad
  33.  *        School of EEE
  34.  *        Nanyang Technological University
  35.  *        Nanyang Avenue
  36.  *        Singapore 2263
  37.  *        Republic of Singapore
  38.  *
  39.  ***************************************************************************/
  40.  
  41. #include <stdio.h>
  42. #include <stdlib.h>
  43. #include <string.h>
  44. #define mask8 255
  45.  
  46. unsigned char   *logmin_b(a, b)              /* pointer to a & b array passed */
  47. unsigned char   *a, *b;
  48.  
  49. {
  50.    unsigned short   pterm, ma, mb, *pm, pos;
  51.    unsigned short   *ca, *mp, m_cnt, a_cnt;
  52.    unsigned  long   m, j, size, addr, count, count1, topow();
  53.    register  long   i, wo, wi;
  54.          char   test;
  55.    unsigned  char   *c, *d, *e, *s, *temp, *cp, *mt, *at, *ad;
  56.    unsigned  char   n, adj, adj0, adji, adjacency(), nspm, cover;
  57.    unsigned  char   *adjacent(), *reduce(), *cpt(), *ssm(), adj_of_mi();
  58.  
  59.  
  60.    mb = *(b+2)<<8 | *(b+1);            /* no. of minterms in b-array */
  61.  
  62.    n    = *a;                          /* no. of variables */
  63.    nspm = *(a+3);                      /* no. of bytes/minterm */
  64.    ma = *(a+2)<<8 | *(a+1);           /* no. of minterms in a-array */
  65.  
  66.    temp = (unsigned char *) malloc(nspm+1);        /* temporary storage */
  67.    if (temp == 0)
  68.       {
  69.      printf("Out of memory -- LOGMIN_B, *temp\n");
  70.      printf("Program terminated - 1\n");
  71.      exit(0);
  72.       }
  73.  
  74.    s = (unsigned char *) malloc(4);                /* header of s-array */
  75.    if (s == 0)
  76.       {
  77.      printf("Out of memory -- LOGMIN_B, *s\n");
  78.      printf("Program terminated - 2\n");
  79.      exit(0);
  80.       }
  81.  
  82.  
  83.    /***********\
  84.     * PHASE I *
  85.    \***********/
  86.  
  87.    pterm = 0;                                /* no. of product term */
  88.    count = 0;                                /* no. of terms stored for phase II */
  89.  
  90.    /***
  91.     ***  DETERMINE ADJACENCY OF ALL MINTERMS AND GENERATE THEIR CPT
  92.     ***/
  93.  
  94.    for (i=0; i<mb; i++)                      /* for all minterms in b-array */
  95.       {
  96.      *b = n;                             /* assign back to n */
  97.  
  98.      memcpy(temp, (b+4+nspm*i), nspm);   /* pick a minterm from b-array */
  99.      c = adjacent(temp, a, 255);         /* obtain the adjacent terms */
  100.      adj = *(c+1);                       /* adjacency of minterm */
  101.      d = cpt(c);                         /* generate CPT */
  102.  
  103.      /***
  104.       ***  MINIMIZE ALL MINTERMS WITH ADJACENCY OF 0 & 1 FIRST
  105.       ***/
  106.  
  107.      if (adj <= 1)                       /* adjacency 0 or 1 */
  108.         {
  109.            s = (unsigned char *) realloc(s,4+n*(pterm+1));   /* more space */
  110.            if (s == 0)
  111.           {
  112.              printf("Out of memory -- LOGMIN_B, *s\n");
  113.              printf("Program terminated - 3\n");
  114.              exit(0);
  115.           }
  116.            memcpy ((s+4+n*pterm),d,n);   /* add CPT to soln array */
  117.            pterm++;                      /* product term count */
  118.  
  119.            b = reduce(c,b,i);            /* remove minterms covered from b-array */
  120.            i = (char) *b;                /* index pointer of b-array */
  121.            mb = *(b+2)<<8 | *(b+1);      /* value of mb altered in b-array */
  122.         }
  123.      else                                /* adj > 1 */
  124.         {
  125.  
  126.            /***
  127.         ***  MINTERMS WITH ADJACENCY GREATER THAN 1, GENERATE SSM AND TEST FOR COVERAGE
  128.         ***/
  129.  
  130.            e = ssm(d);                          /* generate SSM */
  131.            m = topow(*(e+1));                   /* no. of SSM terms */
  132.  
  133.            for (j=0; j<m; j++)                  /* check for SSM coverage */
  134.           {
  135.              memcpy (temp, (e+4+nspm*j), nspm);   /* pick SSM term */
  136.              test = exist (temp, a, ma);
  137.              if (test == -1)                /* minterm not in a-array */
  138.             break;
  139.           }
  140.  
  141.            /***
  142.         ***  ALL SSM COVERED BY THE FUNCTION, SELECT CPT AS PRODUCT TERM
  143.         ***/
  144.  
  145.            if (test == 0)                        /* all SSM's covered by fn */
  146.           {
  147.              if (m > 65536)                  /* too many SSM terms */
  148.             {
  149.                printf("Product Term Too Huge \n");
  150.                printf("Program terminated \n");
  151.                exit(0);
  152.             }
  153.              *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  154.              *(e+2) = (m-1)>>8 & mask8;
  155.              b = reduce(e,b,i);              /* remove minterms covered from b-array */
  156.              i = (char) *b;                  /* index pointer of b-array */
  157.              mb = *(b+2)<<8 | *(b+1);        /* no. of minterms in b-array */
  158.  
  159.              s = (unsigned char *) realloc(s, 4+n*(pterm+1)); /* more space */
  160.              if (s == 0)
  161.             {
  162.                printf("Out of memory -- LOGMIN_B, *s\n");
  163.                printf("Program terminated - 4\n");
  164.                exit(0);
  165.             }
  166.              memcpy((s+4+n*pterm),d,n);     /* add CPT to soln array */
  167.              pterm++;                       /* no. of product terms */
  168.              free(e);                   /* free pointer */
  169.           }
  170.            else
  171.           {
  172.              free(e);                 /* free pointer */
  173.  
  174.              /***
  175.               ***  NOT COVERED, STORE UNCOVERED MINTERMS, ITS CORRESPONDING
  176.               ***  ADJACENCY, ADJACENT TERMS AND CPT FOR PHASE II
  177.               ***/
  178.  
  179.              count++;                       /* no. of terms for phase II */
  180.              if (count==1)                  /* 1st uncovered term */
  181.             {
  182.                ad = (unsigned char *) malloc(2);    /* array of adjacency */
  183.                if (ad==0)
  184.                   {
  185.                  printf("Out of memory -- LOGMIN_B, *ad\n");
  186.                  printf("Program terminated - 5\n");
  187.                  exit(0);
  188.                   }
  189.                cp = (unsigned char *) malloc(n);     /* array of CPT's */
  190.                if (cp==0)
  191.                   {
  192.                  printf("Out of memory -- LOGMIN_B, *cp\n");
  193.                  printf("Program terminated - 6\n");
  194.                  exit(0);
  195.                   }
  196.                mt = (unsigned char *) malloc(4+nspm*count);  /* array of minterms */
  197.                if (mt==0)
  198.                   {
  199.                  printf("Out of memory -- LOGMIN_B, *mt\n");
  200.                  printf("Program terminated - 7\n");
  201.                  exit(0);
  202.                   }
  203.                size = 4 + nspm*(1+adj);                         /* addr counter of at-array */
  204.                at = (unsigned char *) malloc (4+nspm*(1+adj));  /* all adj terms from c-arrays */
  205.                if (at==0)
  206.                   {
  207.                  printf("Out of memory -- LOGMIN_B, *at\n");
  208.                  printf("Program terminated - 8\n");
  209.                  exit(0);
  210.                   }
  211.                ca = (unsigned short *) malloc(2);          /* array of addr of at-array */
  212.                if (ca==0)
  213.                   {
  214.                  printf("Out of memory -- LOGMIN_B, *ca\n");
  215.                  printf("Program terminated - 9\n");
  216.                  exit(0);
  217.                   }
  218.                addr = 0;         /* starting address of at-array */
  219.             }
  220.              else                    /* subsequent uncovered terms */
  221.             {
  222.                ad = (unsigned char *) realloc(ad, count);    /* adjacency */
  223.                if (ad==0)
  224.                   {
  225.                  printf("Out of memory -- LOGMIN_B, *ad\n");
  226.                  printf("Program terminated - 10\n");
  227.                  exit(0);
  228.                   }
  229.                cp = (unsigned char *) realloc(cp,n*count);    /* CPT's */
  230.                if (cp==0)
  231.                   {
  232.                  printf("Out of memory -- LOGMIN_B, *cp\n");
  233.                  printf("Program terminated - 11\n");
  234.                  exit(0);
  235.                   }
  236.                mt = (unsigned char *) realloc(mt,4+nspm*count); /* minterms */
  237.                if (mt==0)
  238.                   {
  239.                  printf("Out of memory -- LOGMIN_B, *mt\n");
  240.                  printf("Program terminated - 12\n");
  241.                  exit(0);
  242.                   }
  243.                size+=4+nspm*(1+adj);                     /* addr counter of at-array */
  244.                at = (unsigned char *) realloc (at,size); /* all adj terms from c-arrays */
  245.                if (at==0)
  246.                   {
  247.                  printf("Out of memory -- LOGMIN_B, *at\n");
  248.                  printf("Program terminated - 13\n");
  249.                  exit(0);
  250.                   }
  251.                ca = (unsigned short *) realloc(ca,2*count);       /* addr of at-array */
  252.                if (ca==0)
  253.                   {
  254.                  printf("Out of memory -- LOGMIN_B, *ca\n");
  255.                  printf("Program terminated - 14\n");
  256.                  exit(0);
  257.                   }
  258.             }
  259.  
  260.              /***
  261.               ***  STORE IN ARRAYS FOR PHASE II
  262.               ***/
  263.  
  264.              *(ad+(count-1)) = adj;                           /* adjacency */
  265.              memcpy((cp+n*(count-1)),d,n);                    /* CPT's */
  266.              memcpy((mt+4+nspm*(count-1)),(b+4+nspm*i),nspm); /* minterms */
  267.              memcpy((at+addr),c,4+nspm*(1+adj));              /* adj terms */
  268.              *(ca+(count-1)) = addr;                   /* addr of at-array */
  269.              addr = size;                              /* update addr */
  270.           }
  271.         }
  272.      free(c);                     /* free pointers */
  273.      free(d);
  274.       }
  275.    count1 = count;                   /* no. of terms for phase II */
  276.  
  277.  
  278.    /************\
  279.     * PHASE II *
  280.    \************/
  281.  
  282.    while (count > 0)               /* some terms stored for phase II */
  283.       {
  284.      /***
  285.       ***  SELECT NEXT MINTERM WITH THE LOWEST ADJACENCY AND AT LEAST ONE OF
  286.       ***  ITS ADJACENT TERMS PREVIOUSLY COVERED
  287.       ***/
  288.  
  289.      adj0 = 255;               /* set to max of 8-bit */
  290.  
  291.      for (i=0; i<count1; i++)               /* do for all adj terms in phase II */
  292.         {
  293.            if (*(ad+i)<adj0 && *(ad+i)!=0)  /* choose minterms with lowest adj */
  294.           {
  295.              if (adj0 != 255)           /* not the first lowest */
  296.             free(mp);
  297.              adj0 = *(ad+i);            /* new lowest value */
  298.              m_cnt = 1;                 /* reset count to 1 */
  299.  
  300.              mp = (unsigned short *) malloc(2);     /* space for pos of lowest adj */
  301.              if (mp==0)
  302.             {
  303.                printf("Out of memory -- LOGMIN_B, *mp\n");
  304.                printf("Program terminated - 15\n");
  305.                exit(0);
  306.             }
  307.              *mp = i;                               /* first element */
  308.           }
  309.            else if (*(ad+i) == adj0)                    /* adj as large */
  310.           {
  311.              m_cnt++;                               /* no. of element in mp-array */
  312.              mp = (unsigned short *) realloc(mp, 2*m_cnt); /* more space */
  313.              if (mp==0)
  314.             {
  315.                printf("Out of memory -- LOGMIN_B, *mp\n");
  316.                printf("Program terminated - 16\n");
  317.                exit(0);
  318.             }
  319.              *(mp+m_cnt-1) = i;            /* elements in mp-array */
  320.           }
  321.         }
  322.  
  323.      /***
  324.       ***  SELECT FROM MP-ARRAY, A MINTERM WITH AT LEAST ONE ADJACENT TERM PREVIOSLY
  325.       ***  COVERED
  326.       ***/
  327.  
  328.      for (i=0; i<m_cnt; i++)                 /* do for all in mp-array */
  329.         {
  330.            adj = *(ad+ *(mp+i));             /* adjacency from ad-array */
  331.  
  332.            c = (unsigned char *) malloc(4+nspm*(1+adj));  /* space for adj terms */
  333.            if (c == 0)
  334.           {
  335.              printf("Out of memory -- LOGMIN_B, *c\n");
  336.              printf("Program terminated - 17\n");
  337.              exit(0);
  338.           }
  339.            memcpy(c, (at+ *(ca+ *(mp+i))), 4+nspm*(1+adj));  /* adj terms from at-array */
  340.  
  341.            for (j=0; j<adj; j++)          /* check for at least 1 adj term covered */
  342.           {
  343.              memcpy(temp, (c+4+nspm*(1+j)),nspm);
  344.              test = exist(temp,b,mb);
  345.              if (test == -1)          /* adj term covered */
  346.             break;
  347.           }
  348.  
  349.            if (test == -1)                /* adj term covered */
  350.           break;
  351.            else
  352.           free(c);                    /* free pointer */
  353.         }
  354.  
  355.      if (test == -1)                      /* adj term covered */
  356.         pos = *(mp+i);                    /* position of minterm required */
  357.      else                                 /* none of adj terms covered */
  358.         {
  359.            adj = *(ad+ *mp);              /* choose adj of 1st minterm */
  360.            pos = *mp;                     /* position of 1st minterm */
  361.  
  362.            c = (unsigned char *) malloc(4+nspm*(1+adj));   /* space for adj terms */
  363.            if (c == 0)
  364.           {
  365.              printf("Out of memory -- LOGMIN_B, *c\n");
  366.              printf("Program terminated - 18\n");
  367.              exit(0);
  368.           }
  369.            memcpy(c, (at+ *(ca+pos)), 4+nspm*(1+adj));     /* adj terms from at-array */
  370.         }
  371.  
  372.      d = (unsigned char *) malloc(n+1);       /* space for corresponding CPT */
  373.      if (d == 0)
  374.         {
  375.            printf("Out of memory -- LOGMIN_B, *d\n");
  376.            printf("Program terminated - 19\n");
  377.            exit(0);
  378.         }
  379.      memcpy(d, (cp+n*pos), n);       /* corresponding CPT from cp-array */
  380.      *(d+n) = '\0';                  /* terminate with NULL string */
  381.  
  382.      e = ssm(d);                     /* generate SSM */
  383.  
  384.      free(d);                        /* free pointers */
  385.      free(mp);
  386.  
  387.      /***
  388.       ***  KEEP SHRINKING THE CPT UNTIL THE SELECTED MINTERM IS COVERED BY THE FUNCTION
  389.       ***/
  390.  
  391.      cover = 0;                      /* coverage status */
  392.      while (!cover)                  /* do until shrinked CPT is covered */
  393.         {
  394.            /***
  395.         ***  OBTAIN AN ARRAY, PM OF POSITIONS OF ADJACENT TERMS, MI WITH THE LARGEST WI
  396.         ***/
  397.  
  398.            wo = -1;                  /* initial value */
  399.            for (i=0; i<adj; i++)     /* do for all adjacent terms */
  400.           {
  401.              memcpy(temp, (c+4+nspm*(i+1)), nspm);  /* pick adjacent term */
  402.  
  403.              wi = adj_of_mi(temp,e,a);              /* obtain wi */
  404.              if (wi>wo)
  405.             {
  406.                if (wo != -1)                    /* not 1st largest wi */
  407.                   free(pm);
  408.                wo = wi;                         /* new largest */
  409.                a_cnt = 1;                       /* set count to 1 */
  410.  
  411.                pm = (unsigned short *) malloc(2);    /* space for pm-array */
  412.                if (pm == 0)
  413.                   {
  414.                  printf("Out of memory -- LOGMIN_B, *pm\n");
  415.                  printf("Program terminated - 20\n");
  416.                  exit(0);
  417.                   }
  418.                *pm = i;              /* 1st element of pm-array */
  419.             }
  420.              else if (wi==wo)            /* wi as large */
  421.             {
  422.                a_cnt++;              /* no. of elements in pm-array */
  423.  
  424.                pm = (unsigned short *) realloc (pm, 2*a_cnt);  /* more space */
  425.                if (pm == 0)
  426.                   {
  427.                  printf("Out of memory -- LOGMIN_B, *pm\n");
  428.                  printf("Program terminated - 21\n");
  429.                  exit(0);
  430.                   }
  431.                *(pm+a_cnt-1) = i;     /* elements of pm-array */
  432.             }
  433.           }
  434.            free(e);                        /* free pointer */
  435.  
  436.            /***
  437.         ***  SELECT FROM PM-ARRAY, AN ADJACENT TERM THAT HAS ALREADY BEEN COVERED
  438.         ***/
  439.  
  440.            for (i=0; i<a_cnt; i++)         /* do for all minterms in pm-array */
  441.           {
  442.              memcpy(temp, (c+4+nspm*(1+ *(pm+i))), nspm); /* pick adj term */
  443.              test = exist(temp,b,mb);
  444.              if (test == -1)                  /* already covered */
  445.             break;
  446.           }
  447.  
  448.            if (i==a_cnt)                          /* select 1st if all not covered */
  449.           i = 0;
  450.  
  451.            adj--;                                 /* no. of adj terms in c-array */
  452.            *(c+1) = adj;                          /* adjacency after shrinking */
  453.            pos = *(pm+i);                         /* position of adj term to be shrinked */
  454.  
  455.            free(pm);                              /* free pointer */
  456.  
  457.         /***
  458.          ***  SHRINK CPT (REMOVE 1 ADJACENT TERM FROM C-ARRAY), GENERATE NEW CPT,
  459.          ***  SSM AND TEST FOR COVERAGE BY FUNCTION
  460.          ***/
  461.  
  462.            memcpy((c+4+nspm*(1+pos)), (c+4+nspm*(2+pos)), nspm*(adj-pos));  /* shrink c-array */
  463.  
  464.            c = (unsigned char*) realloc(c, 4+nspm*(1+adj));   /* decrease space */
  465.            if (c == 0)
  466.           {
  467.              printf("Out of memory -- LOGMIN_B, *c\n");
  468.              printf("Program terminated - 22\n");
  469.              exit(0);
  470.           }
  471.  
  472.            d = cpt(c);                  /* generate CPT */
  473.            e = ssm(d);                  /* generate SSM */
  474.            m = topow(*(e+1));           /* no. of SSM terms */
  475.  
  476.            for (i=0; i<m; i++)          /* check SSM coverage by function */
  477.           {
  478.              memcpy(temp, (e+4+nspm*i), nspm);   /* pick SSM term */
  479.              test = exist(temp,a,ma);
  480.              if (test == -1)                     /* SSM not covered */
  481.             break;
  482.           }
  483.  
  484.            /***
  485.         ***  SHRINKED SSM COVERED BY FUNCTION, REDUCE B-ARRAY AND
  486.         ***  SELECT SHRINKED CPT AS PRODUCT TERM
  487.         ***/
  488.  
  489.            if (test==0)                      /* SSM covered */
  490.           {
  491.              if (m > 65536)                  /* too many SSM terms */
  492.             {
  493.                printf("Product Term Too Huge \n");
  494.                printf("Program terminated \n");
  495.                exit(0);
  496.             }
  497.              *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  498.              *(e+2) = (m-1)>>8 & mask8;
  499.              b = reduce(e, b, m);        /* remove minterms covered from b-array */
  500.              mb = *(b+2)<<8 | *(b+1);    /* no. of minterms in b-array */
  501.  
  502.              count = mb;                 /* count of no. of minterms not covered */
  503.  
  504.              s = (unsigned char *) realloc(s, 4+n*(pterm+1));   /* more space */
  505.              if (s == 0)
  506.             {
  507.                printf("Out of memory -- LOGMIN_B, *s\n");
  508.                printf("Program terminated - 23\n");
  509.                exit(0);
  510.             }
  511.              memcpy ((s+4+n*pterm), d, n);     /* add shrinked CPT to soln array */
  512.              pterm++;                          /* no. of product terms */
  513.  
  514.              cover = 1;                        /* coverage status */
  515.  
  516.              /***
  517.               ***  FLAG TERMS COVERED IN THE AD-ARRAY
  518.               ***/
  519.  
  520.              for (i=0; i<m; i++)               /* flag terms just covered */
  521.             {
  522.                for (j=0; j<count1; j++)    /* do for all terms in mt-array */
  523.                   {
  524.                  test = memcmp((e+4+nspm*i), (mt+4+nspm*j), nspm);
  525.                  if (test==0)
  526.                     {
  527.                        *(ad+j) = 0;    /* flag the adjacency to indicate coverage */
  528.                        break;
  529.                     }
  530.                   }
  531.             }
  532.              free(e);            /* free pointer */
  533.           }
  534.            free (d);                 /* free pointer */
  535.         }
  536.      free(c);                        /* free pointer */
  537.       }
  538.  
  539.    if (count1>0)                  /* some terms stored for phase II */
  540.       {
  541.      free(ad);                /* free pointers */
  542.      free(cp);
  543.      free(mt);
  544.      free(at);
  545.      free(ca);
  546.       }
  547.  
  548.    *s = n;                        /* no. of variables */
  549.    *(s+1) = pterm & mask8;        /* no. of product terms in 2 bytes */
  550.    *(s+2) = pterm>>8 & mask8;
  551.  
  552.    free(temp);                    /* free pointer */
  553.    free(a);
  554.    free(b);
  555.  
  556.    return(s);                     /* return solution array */
  557. }
  558.  
  559.